package 数据结构.树;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-26
 */
public class JZ79判断是不是平衡二叉树 {
    //平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
    //自顶向下 递归
    /**
     *  step 1：第一个函数递归遍历二叉树所有节点。
     * step 2：对于每个节点判断，调用第二个函数获取子树深度。
     * step 3：第二个函数递归获取子树深度，只需要不断往子节点深度遍历，累加左右深度的较大值。
     * step 4：根据深度判断该节点下的子树是否为平衡二叉树。
     * */
        //计算该子树深度函数
        public int deep(TreeNode root){
            //空节点深度为0
            if(root == null)
                return 0;
            //递归算左右子树的深度
            int left = deep(root.left);
            int right = deep(root.right);
            //子树最大深度加上自己
            return (left > right) ? left + 1 : right + 1;
        }

        public boolean IsBalanced_Solution(TreeNode root) {
            //空树为平衡二叉树
            if (root == null)
                return true;
            int left = deep(root.left);
            int right = deep(root.right);
            //左子树深度减去右子树相差绝对值大于1
            if(left - right > 1 || left - right < -1)
                return false;
            //同时，左右子树还必须是平衡的
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);
        }



        //自底向上
        public boolean IsBalanced_Solution2(TreeNode root) {
            if(root == null)
                return true;
            return getdepth(root) != -1;
        }

        public int getdepth(TreeNode root) {
            if(root == null)
                return 0;
            //递归计算当前root左右子树的深度差
            int left = getdepth(root.left);
            //当前节点左子树不平衡，则该树不平衡
            if(left < 0)
                return -1;
            int right = getdepth(root.right);
            //当前节点右子树不平衡，则该树不平衡
            if(right < 0)
                return -1;

            //计算深度差
            return Math.abs(left - right) > 1 ? -1 : 1 + Math.max(left, right);
        }
    }



